#include <bits/stdc++.h>

using namespace std;

// 雇佣K名工人的最低成本
// 有n名工人，给定两个数组quality和wage
// 其中quality[i]表示第i名工人的工作质量，其最低期望工资为wage[i]
// 现在我们想雇佣k名工人组成一个工资组
// 在雇佣一组k名工人时，我们必须按照下述规则向他们支付工资：
// 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资
// 工资组中的每名工人至少应当得到他们的最低期望工资
// 给定整数k，返回组成满足上述条件的付费群体所需的最小金额
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/

class Solution
{
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) 
    {
        int n = quality.size();
        // // 薪水 / 质量的比例，质量
        pair<double, int> employees[n];
        for(int i = 0; i < n; ++i)
        {
            employees[i] = {(double)wage[i] / quality[i], quality[i]};
        }
        // 根据比例排序，比例小的在前，比例大的在后
        sort(employees, employees + n);
        // 大根堆，用来收集最小的前k个质量数值
        priority_queue<int> heap;
        // 堆里，最小的前k个质量数值，总和是多少
        int qualitySum = 0;
        double ans = INT_MAX;
        for(int i = 0, curQuality; i < n; ++i)
        {
            curQuality = employees[i].second;
            double ratio = employees[i].first;
            if(heap.size() < k) // 堆没满
            {
                qualitySum += curQuality;
                heap.push(curQuality);
                // 刚好 k 个人
                if(heap.size() == k)
                {
                    ans = min(ans, ratio * qualitySum);
                }
            }
            else
            {
                // 堆满了
                if(heap.top() > curQuality)
                {
                    qualitySum += curQuality - heap.top();
                    heap.pop();
                    heap.push(curQuality);
                    ans = min(ans, ratio * qualitySum);
                }
            }
        }
        return ans;
    }
};